1. Field of the Invention
The present invention relates to a digital communication system, and more particularly to a state metric memory of a viterbi decoder for a digital communication system.
2. Discussion of Related Art
Generally, a viterbi decoder is frequently used in a transmission-reception apparatus for decoding via an optimal path in fields of a satellite communication and a digital communication. The viterbi decoder is a fairly recent technique and is shown in FIG. 1(a). The viterbi decoder generally includes a branch metric calculator 10 calculating branch metrics from received code symbols and voluntary hypotheses by using a look-up table; an adder/comparator/selector (ACS) 20 adding the branch metrics and the current-state metrics, comparing path metrics, and selecting an optimal path metric; a memory 30 reading and writing the current-state metrics and the next-state metrics; and an address generator 40 selectively generating control signals for designating addresses of the memory to read and write the current or next-state metrics.
In a viterbi decoding method, a trellis diagram is built for all the transmitted code symbols. In the trellis diagram, the distance values of each node corresponding to input data are calculated and the distance values for each potential paths for decoding are accumulated. The path having a minimum accumulated distance value, i.e. the minimum evaluation quantity is determined to be a survival path.
The addresses of the viterbi decoder are generated through a process in which the current state metrics are read out from the memory according to a fixed period, thereby renewing the addresses for the next state metrics. Thus, the next state metrics are written into the renewed addresses of the memory.
To designate the optimal next-state metrics to be written according to the fixed period after the current-state metrics has been read, eight reading and writing operations must be executed. For example, (000,001xe2x86x92000), (010,011xe2x86x92001), (100,101xe2x86x92010), (110,111xe2x86x92011), (000,001xe2x86x92100), (010,011xe2x86x92101), (100,101xe2x86x92110) and (110,111xe2x86x92111) are executed in order to actively perform all state transitions as shown in the trellis diagram of FIG. 2.
The state metrics in the eight states generated through the above eight reading and writing operations are regarded as the current-state metrics and the eight reading and writing operations are repeated again for a set of next state metrics. For a smooth implementation of this repeated state exchange of the metrics, the memory must store, at any given point of time, all the current-state metrics read according to the fixed period and must also have memory space for storing the next-state metrics written according to the fixed period.
Thus, if the memory space capable of storing all the current-state metrics is N, the memory requires additional memory space of N for writing the next-state metrics. In other words, the memory space capacity must overall be 2N to completely accomplish the above repeated state exchange of the metrics.
The states in the trellis diagram of FIG. 2 are limited by a constraint length. The number of stages in the encoder, which is equal to one more than the number of delay elements, is known as the constraint length. Supposing that C is the constraint length, the states exist in a range between xe2x80x9c0xe2x80x9d and xe2x80x9c2c-1-1xe2x80x9d. Thus, the constraint length in the trellis diagram of FIG. 2 would be four resulting in eight states.
The operations of the state metric memory in the viterbi decoder as shown in FIG. 1(a) will be described in reference to FIG. 2. The memory 30 includes four submemories M100 to M400 as shown in FIG. 1(b). All four memories are necessary for the current-state metrics read according to the fixed period and the next-state metrics written according to the fixed period.
Particularly, the first and second memories M100, M200 are for the current-state metrics, and third and fourth memories M300, M400 are for the next-state metrics. After a conversion from the current-states to the next-states, as shown in FIG. 2, the first and second memories M100, M200 write the metrics of the next-states while the third and fourth memories M300, M400 read the metrics of the current-states.
Also, the address generator 40 includes a counter 41 and a controller 42 controlling the counter 41. The address generator 40 outputs control signals for designating a domain of the memory. The metrics of the first current-states 0=000 and 1=001, stored initially in the first and second memories M100, M200 are read by according to the control signals output from the address generator 40 and are input to the ACS 20.
Utilizing a look up table, the ACS 20 adds the branch metrics calculated from the code symbols and hypotheses transmitted within a fixed period, and the metrics of the current-states 0=000 and 1=001, respectively. The ACS compares summed path metrics of the metrics and selects an optimal path metric having the minimum evaluation quantity, thereby producing each path metrics. Such optimal path metric is the survival path metric and is written in the third memory M300 as the next-state xe2x80x980=000.xe2x80x99
Upon completion of the above process, the address generator 40 reads the metrics of the following current-states 2=010 and 3=011, stored at the first and second memories M100 and M200, and writes a second survival path metric in the fourth memory M400 as the next-state xe2x80x981=001xe2x80x99 through the same process as the above process. Similarly, the remaining current-state metrics of the first and second memories M100 and M200 are read continuously according to a fixed period, and the selected survival path metrics are written according to the fixed period in the third and fourth memories M300 and M400, respectively, as the next-states through the process as discussed above.
During the process, the current-state metrics of the first and second memories M100 and M200 are read according to the control signals in a fixed period. The survival path metrics are sequentially written in the third M300 and fourth M400 memories as the next-states, thereby a first 8-state transition process is completed. FIG. 3 shows a sequential state transition process of the state metric memory based upon the conventional technique.
Referring to FIG. 3, the first eight current-state metrics are read from memories M100 and M200 by a fixed period, and are sequentially and alternately written into memories M300 and M400 by the fixed period. The eight current-state metrics are assigned to the next-state metrics by a designated sequence in a fixed period as follows {000 and 001xe2x86x92010 and 011xe2x86x92100 and 101xe2x86x92110 and 111xe2x86x92000 and 001xe2x86x92010 and 011xe2x86x92100 and 101xe2x86x92110 and 111}.
In assigning the current-state metrics, the first next-state metric of 0xe2x80x2 is designated to assign the first current-state metrics 0=000 and 1=001 from the memories M100, M200 to the third memory M300. A second current-state metrics 2=010 and 3=011 from the memories M100 and M200 are designated to a second next-state metric 1xe2x80x2 in the fourth memory M400. A third current-state metrics 4=100 and 5=101 from the memories M100 and M200 are designated to a third next-state metric 2xe2x80x2 in the third memory M300. A fourth current-state metrics 6=110 and 7=111 from the memories M100 and M200 are designated to a fourth next-state metric 3xe2x80x2 in the fourth memory M400.
The address generator 40 generates control signals to output the metrics of the first and second current-state metrics 0=000, 1=001 from the first and second memories M100, M200 in a predetermined order as discussed above and shown in FIG. 3(a) to (axe2x80x2).
Accordingly, a fifth current-state metrics 0=000, 1=000 from the memories M100, M200 are designated to a fifth next-state metric 4xe2x80x2 in the third memory M300. A sixth current-state metrics 2=010, 3=011 from the memories M100, M200 are designated to a sixth next-state metric 5xe2x80x2 in the fourth memory M400. A seventh current-state metrics 4=100, 5=101 from the memories M100, M200 are designated to a seventh next-state metric 6xe2x80x2 in the third memory M300. An eighth current-state metrics 6=110, 7=111 from the memories M100, M200 are designated to an eighth next-state metric 7xe2x80x2 in the fourth memory M400.
Upon completion of assigning the eight current-state metrics, the designated next-state metrics in the third and fourth memories M300, M400, namely 0xe2x80x2=000, 1xe2x80x2=010, 3xe2x80x2=011, 4xe2x80x2=100, 5xe2x80x2=101, 6xe2x80x2=110 and 7xe2x80x2=111 become the current-state metrics, and as current-state metrics repeat the above discussed process for designating a following set of next-state metrics. Because the next-state metrics become the current-state metrics at a certain point in time, the memory must store all the current-state metrics in the first and second memories M100, M200 as well as requiring additional memory domain with the same capacity as the first and second memories M100, M200.
In sum, in an initial state (a), the first and second memories M100, M200 already store metrics of the current-states 0,1,2,3,4,5,6,7, and alternately write the metrics of the next-states 0xe2x80x2,1xe2x80x2,2xe2x80x2,3xe2x80x2,4xe2x80x2,5xe2x80x2,6xe2x80x2,7xe2x80x2 to the third and fourth memories M300, M400 in a designated sequence. Upon completion of the writing the metrics of the next states as shown in part (axe2x80x2), the roles of the memories change. Namely, the states of the third and fourth memories M300, M400 are changed to the current-states, and the states of the first and second memories M100, M200 are changed to accommodate the following next-states to repeat the reading and writing process.
As a result, in the state metric memory of the viterbi decoder according to the conventional art, both a memory space for storing the current-state metrics and a memory space for writing the next-state metrics is required. Thus, the total capacity of the memory space must be twice the space necessary to store the current-state metrics to correct errors of received code symbols and to decode via an optimal path.
The additional memory capacity requirements not only run counter to a lightness/thinness/simplicity characteristic trend in the communicative instruments of the communication fields, but also cause a cost increase especially in a mobile radio communication system requiring a memory of high speed and large capacity.
Accordingly, an object of the present invention is to solve at least the problems and disadvantages of the related art.
An object of the present invention is to provide a state metric memory of a viterbi decoder capable of simultaneously storing survival path metrics generated from current-state metrics and storing two next-state metrics.
Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objects and advantages of the invention may be realized and attained as particularly pointed out in the appended claims.
To achieve the objects and in accordance with the purposes of the invention, as embodied and broadly described herein, a state metric memory of a viterbi decoder comprises a calculating unit calculating a plurality of branch metrics from code symbols and hypotheses; a path generating unit producing each metric paths utilizing numerous state metrics of an initial state or a previous state and the branch metrics; a memory simultaneously storing current-state metrics read and next-state metrics written in the path generating unit; and a control unit providing the memory with address signals which control operations for reading and writing the current-state metrics and the next-state metrics.
In another embodiment of the present invention, a decoding method using a state metric memory of a viterbi decoder includes the steps of calculating a plurality of branch metrics from code symbols and hypotheses; producing each metric paths by utilizing numerous state metrics of an initial state or a previous state and the branch metrics; reading current-state metrics and writing next-state metrics, and simultaneously storing the metrics; and determining the stored state metrics as the current-state metrics and repeating the steps.
According to the present invention, a limited memory space is efficiently used and a communication system having a high-speed/large capacity can be processed without an additional memory capacity.